package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer 13. 机器人的运动范围
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/29 16:08
 */
public class MovingCount {

    private int[] arr;
    private int k;
    private int m;
    private int n;
    private int c;

    public int movingCount(int m, int n, int k) {
        this.arr = new int[n * m];
        this.m = m;
        this.n = n;
        this.k = k;
        find(0, 0);
        return c;
    }

    private void find(int x, int y) {
        if (x < 0 || y < 0 || x == m || y == n) {
            return;
        }
        int item = x * n + y;
        if (arr[item] == 1) {
            return;
        }
        arr[item] = 1;
        int x1 = x;
        int y1 = y;
        item = 0;
        while (x1 != 0) {
            item += x1 % 10;
            x1 /= 10;
        }
        while (y1 != 0) {
            item += y1 % 10;
            y1 /= 10;
        }
        if (item > k) {
            return;
        }
        c++;
        find(x + 1, y);
        find(x, y + 1);
    }

}
